#include<bits/stdc++.h>
using namespace std;

typedef pair<int, int> comb_state_type;
typedef pair<int, int> things_feature_type;
#define weight(a) (a.first)
#define val(a) (a.second)

int main() {
    int things, volume;
    cin >> things >> volume;
    
    vector<things_feature_type> all_things(things);
    int tmp;
    for (int i = 0; i < things; ++i) {
        cin >> tmp;
        weight(all_things[i]) = tmp;
        cin >> tmp;
        val(all_things[i]) =  tmp;
        //cout << tmp << endl;
    }

    vector<vector<comb_state_type>> state_matrix(things+1, vector<comb_state_type>(volume+1));
    // initial state
    for (auto state_pair: state_matrix[0]) {
        state_pair.first = 0;
        state_pair.second = -1;
    }
    for (int i = 0; i < things+1; ++i) {
        state_matrix[i][0].first = 0;
        state_matrix[i][0].second = 0;
    }
    
    for (int i = 1; i < things+1; ++i) {
        for (int j = 1; j < volume+1; ++j) {
            // state movement for question 1
            if (j >= weight(all_things[i-1])) {
            state_matrix[i][j].first = max(state_matrix[i-1][j].first, 
                                           state_matrix[i-1][j-weight(all_things[i-1])].first+val(all_things[i-1]));
                //cout << state_matrix[i][j].first;
            } else {
                state_matrix[i][j].first = state_matrix[i-1][j].first;
            }
            // state movement for question 2
            if (state_matrix[i-1][j].second != -1 && (j >= weight(all_things[i-1])) && (state_matrix[i-1][j-weight(all_things[i-1])].second != -1)) {
                state_matrix[i][j].second = max(state_matrix[i-1][j].second, state_matrix[i-1][j-weight(all_things[i-1])].second + val(all_things[i-1]));
                
                
            } else if (state_matrix[i-1][j].second != -1) {
                state_matrix[i][j].second = state_matrix[i-1][j].second;
            } else if ((j >= weight(all_things[i-1])) && (state_matrix[i-1][j-weight(all_things[i-1])].second != -1)) {
                state_matrix[i][j].second = state_matrix[i-1][j-weight(all_things[i-1])].second + val(all_things[i-1]);
                
            } else {
                state_matrix[i][j].second = -1;
            }
            cout << state_matrix[i][j].second << " ";
        }
        
    }
    
    cout << state_matrix[things][volume].first << endl;
    cout << max(state_matrix[things][volume].second, 0) << endl;
    
    return 0;
}